package com.itheima.leetcode.od.b.graph.bipartitegraph;

import java.util.Arrays;
import java.util.stream.IntStream;

/**
 * (C卷,200分)- 矩阵匹配（Java & JS & Python & C）
 * <p>
 * 题目描述
 * <p>
 * 从一个 N * M（N ≤ M）的矩阵中选出 N 个数，任意两个数字不能在同一行或同一列，求选出来的 N 个数中第 K 大的数字的最小值是多少。
 * <p>
 * 输入描述
 * <p>
 * 输入矩阵要求：1 ≤ K ≤ N ≤ M ≤ 150
 * <p>
 * 输入格式：
 * <p>
 * N M K
 * <p>
 * N*M矩阵
 * <p>
 * 输出描述
 * N*M 的矩阵中可以选出 M! / N! 种组合数组，每个组合数组种第 K 大的数中的最小值。无需考虑重复数字，直接取字典排序结果即可。
 * <p>
 * 备注
 * 注意：结果是第 K 大的数字的最小值
 * <p>
 * 用例
 * <p>
 * 输入	3 4 2
 * <p>
 * 1 5 6 6
 * <p>
 * 8 3 4 3
 * <p>
 * 6 8 6 3
 * <p>
 * 输出	3
 * 说明
 * N*M的矩阵中可以选出 M！/ N！种组合数组，每个组合数组种第 K 大的数中的最小值；
 * <p>
 * 上述输入中选出数组组合为：
 * <p>
 * 1,3,6;
 * <p>
 * 1,3,3;
 * <p>
 * 1,4,8;
 * <p>
 * 1,4,3;
 * <p>
 * ......
 * <p>
 * 上述输入样例中选出的组合数组有24种，最小数组为1,3,3，则第2大的最小值为3
 */
public class MatrixMatching {
    public static void main(String[] args) {
        /*Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        m = sc.nextInt();
        k = sc.nextInt();

        int min = 1;
        int max = Integer.MIN_VALUE;

        matrix = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                matrix[i][j] = sc.nextInt();
                max = Math.max(max, matrix[i][j]);
            }
        }*/

        int n = 3;
        int m = 4;
        int k = 2;

        int[][] matrix = Arrays.stream("1 5 6 6\n8 3 4 3\n6 8 6 3".split("\n"))
                .map(s -> Arrays.stream(s.split(" "))
                        .mapToInt(Integer::parseInt)
                        .toArray())
                .toArray(int[][]::new);

        System.out.println(getResult(k, matrix));
    }

    private static int getResult(int k, int[][] matrix) {
        int min = Arrays.stream(matrix)
                .flatMapToInt(IntStream::of)
                .min()
                .orElse(Integer.MAX_VALUE);

        int max = Arrays.stream(matrix)
                .flatMapToInt(IntStream::of)
                .max()
                .orElse(Integer.MIN_VALUE);

        // 二分枚举第K大值
        // 其实就是换一种视角，假设mid就是被枚举出来的N个数中的第K大值，计算是否存在N-K+1个不大于它的值
        int ans = -1;
        while (min <= max) {
            // mid就是被枚举出来的N个数中的第K大值(注意审题第k大是倒序排序)
            int mid = (min + max) >> 1;

            // 检查mid作为N个数中第K大值时，是否存在N-K+1个不大于它的值
            if (check(k, mid, matrix)) {
                ans = mid;
                max = mid - 1;
            } else {
                min = mid + 1;
            }
        }

        return ans;
    }

    /**
     * 关于二分图可以参考这些视频：
     * <p>
     * <a href="https://blog.csdn.net/u013384984/article/details/90718287">匈牙利算法</a>
     * <p>
     * <a href="https://blog.csdn.net/zack_liu/article/details/123396889">匈牙利算法及KM算法详解</a>
     *
     * @param k
     * @param kth
     * @param matrix
     * @return
     */
    public static boolean check(int k, int kth, int[][] matrix) {
        int n = matrix.length;
        int m = matrix[0].length;

        // 利用二分图最大匹配来求解，小于等于kth（第K大值）的元素个数（即二分图最大匹配）
        int smallerCount = 0;

        // 记录每个行号的匹配成功的列号
        int[] match = new int[m];
        // 初始时每个行号都处于未配对状态，此时将行号配对的列号赋值为-1
        Arrays.fill(match, -1);

        // 遍历列号，每个列号对互相心仪的行号发起配对请求
        for (int i = 0; i < n; i++) {
            // 记录增广路访问过的行号
            boolean[] vis = new boolean[m];
            if (dfs(i, kth, match, vis, matrix)) {
                smallerCount++;
            }
        }

        return smallerCount >= n - k + 1;
    }

    public static boolean dfs(int i, int kth, int[] match, boolean[] vis, int[][] matrix) {
        int m = matrix[0].length;

        // 列号 i 发起了配对请求
        // 遍历每一个行号j
        for (int j = 0; j < m; j++) {
            // 如果当前行号j未被增广路探索过 && 当前行j列号i可以配对（如果行列号位置(i,j)对应矩阵元素值小于等于kth（第K大值），则可以配对）
            if (!vis[j] && matrix[i][j] <= kth) {
                vis[j] = true;

                // 如果对应行号j未配对，或者，已配对但是配对的列号match[j]可以找到其他行号重新配对
                if (match[j] == -1 || dfs(match[j], kth, match, vis, matrix)) {
                    // 则当前列号i 和 行号j 可以配对
                    match[j] = i;
                    return true;
                }
            }
        }

        return false;
    }
}